Programmable logic devices (PLDs), such as field-programmable gate arrays (FPGAs), are user-programmable integrated circuits that can be programmed to implement user-defined logic circuits. In a typical FPGA architecture (for example, a Virtex-II Pro FPGA available from Xilinx Inc. of San Jose Calif.), an array of configurable logic blocks (CLBs) and a programmable interconnect structure are surrounded by a ring of programmable input/output blocks (IOBs). The programmable interconnect structure comprises interconnects and configuration memory cells. Each of the CLBs and the IOBs also includes configuration memory cells. The contents of the configuration memory cells determine how the CLB, the programmable interconnect structure or the IOB is configured. Additional resources, such as multipliers, block random access memory and a microprocessor are also included on the FPGA for use in the user-defined circuit.
To realize a user-defined circuit, configuration data is loaded into the configuration memory cells such that the CLBs and IOBs are configured to emulate particular circuit components used in the user-defined circuit. Configuration data is also loaded into the configuration memory cells of the programmable interconnect structure such that the programmable interconnect structure connects the various configured CLBs and IOBs in a desired manner to realize the user-defined circuit.
There is a market demand for PLDs to perform ever more complex tasks, such as the multiplication of complex numbers. To efficiently multiply complex numbers, dedicated multiplier resources for handling complex numbers could be provided on an FPGA. One application for the multiplication of complex numbers would be in digital signal processing. Where a digitized complex data stream is supplied to one input of a mixer, and where a complex data stream representing the local oscillator frequency is supplied to the other input of the mixer, complex number multiplication can be used to calculate the complex output of the mixer.
One conventional way to multiply complex numbers involves real number multiplier components. Each multiplier component outputs the cross product of two inputs. Multiplier components are used to calculate the cross products that make up the arithmetic solution to the multiplication of two complex numbers. The product of a first complex number XRE+iXIM times a second complex number YRE+iYIM can be expressed in terms of four cross products XREYRE, XIMYIM, XREYIM, and YREXIM, where (XREYRE−XIMYIM) is the real part of the product and (XREYIM+YREXIM) is the imaginary part of the product. Thus, one multiplier component is used to calculate each of the four cross products. A total of four multiplier components are used. An adder and a subtractor are typically required to combine the cross products to yield the complex solution.
FIG. 1 (Prior Art) shows a multiplier component 1 within an FPGA as used in one conventional multiplication method. Multiplier component 1 includes a multiplier 2, a dual-ported block RAM 3, an input multiplexer 4 and an output demultiplexer 5. dual-ported block RAM 3 is coupled to input multiplexer 4 by two 36-bit input buses 6 and 7. Output demultiplexer 5 receives data from dual-ported block RAM 3 on two 36-bit output buses 8 and 9. In order to conserve integrated circuit area, input buses 6 and 7 are shared and are also used to supply input values to multiplier 2. Similarly, output buses 8 and 9 can be used to receive output values from multiplier 2. Accordingly, when multiplier component 1 is in operation, access to block RAM 2 is restricted by the number of bits of input buses 6 and 7 used to provide data to multiplier 2. A set of memory cells configures the width of block RAM 3. Block RAM 3 can be set to output words of width N, where N equals 1, 2, 4, 9, 18 or 36. When N is 36, multiplier 2 is not used.
FIG. 2 (Prior Art) illustrates how four multipliers from four multiplier components are used to perform complex multiplication employing conventional techniques. Each complex number to be multiplied has a real part and an imaginary part. Four multipliers are required to calculate the four cross products of the solution.
The difference of two cross products is calculated by subtractor 10 to obtain the real part of the solution (XREYRE−XIMYIM), and the other two cross products are added by an adder to obtain the imaginary part of the solution (XREYIM+YREXIM). The adders are implemented in the CLBs. Memory in four RAM blocks is restricted because four multiplier components with shared interconnects are used.
The above-described problem of restricting access to block RAM might be solved by providing additional dedicated interconnects. Providing additional dedicated interconnects, however, may make the structure larger, thereby increasing production cost. The resulting FPGA would be less desirable, especially for applications that do not require complex multiplication.
A second conventional way to multiply complex numbers involves expressing the arithmetic solution in terms of (XRE−XIM)YIM, thereby reducing to three the number of cross products in the solution. This way reduces to three the number of multiplier components used in the multiplier circuit to calculate the solution. Again, an adder and a subtractor are typically required to combine the cross products to yield the complex solution. Moreover, in this second conventional method, addition is performed both before and after the multiplication, thereby increasing the time for computation.
Thus an improved way of multiplying complex numbers that reduces the number of multiplier components is sought. A circuit and method for including a multiplier resource in a PLD is sought that increases the availability of block RAM through existing interconnects when the multiplier is performing complex multiplication and that reduces the number of multiplier components used to perform complex multiplication.